int n,rk[MAXN],sa[MAXN],tmp[MAXN],fir[MAXN],sec[MAXN],buc[MAXN];
char a[MAXN];
void cal_rk()
{
	int m=127;
	for(int i=1;i<=n;++i)++buc[(int)a[i]];
	for(int i=1;i<=m;++i)buc[i]+=buc[i-1];
	for(int i=1;i<=n;++i)rk[i]=buc[(int)a[i]-1]+1;
	for(int len=1;len<=n;len<<=1)
	{
		for(int i=1;i<=n;++i)fir[i]=rk[i],sec[i]=i+len>n?0:rk[i+len];
		fill(buc,buc+1+n,0);
		for(int i=1;i<=n;++i)++buc[sec[i]];
		for(int i=1;i<=n;++i)buc[i]+=buc[i-1];
		for(int i=n;i;--i)tmp[buc[sec[i]]--]=i;
		fill(buc,buc+1+n,0);
		for(int i=1;i<=n;++i)++buc[fir[i]];
		for(int i=1;i<=n;++i)buc[i]+=buc[i-1];
		for(int i=n;i;--i)sa[buc[fir[tmp[i]]]--]=tmp[i];
		bool flag=true;
		for(int i=1;i<=n;++i)
		{
			rk[sa[i]]=rk[sa[i-1]];
			if(fir[sa[i]]==fir[sa[i-1]]&&sec[sa[i]]==sec[sa[i-1]])flag=false;
			else ++rk[sa[i]];
		}
		if(flag)break;
	}
	return;
}
void cal_height()
{
	int j,k=0;
	for(int i=1;i<=n;++i)
	{
		if(k)--k;
		j=sa[rk[i]-1];
		while(s[i+k]==s[j+k])++k;
		height[rk[i]]=k;
	}
	return;
}
